package org.example.struct.array3;

import java.util.*;

/**
 * @author liyishan
 * @date 2024/6/19 10:36
 * @apiNote
 */

public class Test02713MaxIncreasingCells {

    public static void main(String[] args) {
        int[][] mat = {{3,1},{3,4}};
        System.out.println(maxIncreasingCells(mat));
    }

    public static int maxIncreasingCells(int[][] mat) {
        int m = mat.length, n = mat[0].length;
        Map<Integer, List<int[]>> map = new HashMap<>();
        int[] row = new int[m];
        int[] col = new int[n];
        for(int i = 0; i < m; ++i){
            for(int j =0;j<n;j++){
                map.putIfAbsent(mat[i][j],new ArrayList<>());
                map.get(mat[i][j]).add(new int[]{i,j});
            }
        }
        List<Integer> keys = new ArrayList<>(map.keySet());
        Collections.sort(keys);
        for(int key : keys){
            List<int[]> pos = map.get(key);
            List<Integer> res = new  ArrayList<>();
            for(int[] arr: pos){
                res.add(Math.max(row[arr[0]],col[arr[1]])+1);
            }
            for(int i = 0;i<pos.size();i++){
                int[] arr = pos.get(i);
                int d = res.get(i);
                row[arr[0]] = Math.max(row[arr[0]],d);
                col[arr[1]] = Math.max(col[arr[1]],d);
            }

        }
        return Arrays.stream(row).max().getAsInt();
    }
}
